#include "ax_sort.h"
#include "ax_printf.h"
void ax_quick_sort(int *array, int left,int right)
{
    if(left>=right)
    {
        return;
    }

    int l = left;
    int r = right;

    int key = array[l];

    while(l < r)
    {
        while(l < r && array[r] > key)
        {
            r--;
        }

        if(l < r)
        {
            int org = array[l];
            array[l] = array[r];

            printf("{{right set array[%d](%d) <-- array[%d](%d)  [%d:%d] key:%d\n",l,org,r,array[r],left,right,key);
            ax_printints(array,10,"right");
            l++;
            printf("l:%d r:%d }}\n\n",l,r);
        }

        while(l < r && array[l] < key)
        {
            l++;
        }

        if(l < r)
        {
            int org = array[r];
            array[r] = array[l];
            printf("{{left set array[%d](%d) <-- array[%d](%d) [%d:%d] key:%d\n",r,org,l,array[l],left,right,key);
            ax_printints(array,10,"left");
            r--;
            printf("l:%d r:%d }}\n\n",l,r);
        }

    }

    int org = array[l];
    array[l] = key;
    printf("{{put array[%d](%d) <-- key:%d [%d:%d] l:%d r:%d key:%d\n",l,org,key,left,right,l,r,key);
    ax_printints(array,10,"put array");
    printf("l:%d r:%d }}\n\n",l,r);

    ax_quick_sort(array, left, l-1);
    ax_quick_sort(array, l+1, right);
}

void ax_bubble_sort(int *array, int len)
{
    for(int i=1;i<len;i++)
    {
        for(int j=0;j<len-i;j++)
        {
            if(array[j]>array[j+1])
            {
                int temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
            }
        }
    }
}

void ax_select_sort(int *array, int len)
{
   for(int i=0;i<len-1;i++)
   {
       int min = i;
       for(int j=i+1;j<len;j++)
       {
           if(array[j] < array[min])
           {
               min = j;
           }
       }

       if(min!=i)
       {
           int temp = array[i];
           array[i]=array[min];
           array[min] = temp;
       }
   }
}

void ax_insert_sort(int *array, int len)
{
    for(int i=1;i<len;i++)
    {
        int j=i;
        int data_need_insert = array[i];
        while(j>0)
        {
            if(array[j-1]>data_need_insert)
            {
                array[j] = array[j-1];
                j--;
            }
            else
            {
                break;
            }
        }
        array[j] = data_need_insert;
     }
}

/**
 * @brief ax_shell_sort
 * @param array
 * @param len
 */
void ax_shell_sort(int *array, int len)
{
    for(int step=len/2;step>=1;step/=2)
    {
        for(int i=step;i<len;i+=step)
        {
            int j=i;
            int data_need_insert = array[i];
            while(j>0)
            {
                if(array[j-step]>data_need_insert)
                {
                    array[j] = array[j-step];
                    j-=step;
                }
                else
                {
                    break;
                }
            }
            array[j] = data_need_insert;
         }
    }
}
